package com.backpack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

//二叉树 动态规划
public class HouseRobberIII0114_337 {
    public int rob(TreeNode root) {
        int[] result = robTree(root);
        return Math.max(result[0],result[1]); //result[0]表示不偷当前节点得到的最大值，result[1]表示偷当前节点得到的最大值。
    }

    private int[] robTree(TreeNode node) {
        int[] res = new int[2];
        //递归
        //终止条件
        if(node == null) return res;

        // 动态规划 dp数组用于记录状态，含义：dp[0]表示不偷当前节点得到的最大值，dp[1]表示偷当前节点得到的最大值。
        //递归公式：
        // 后序遍历
        int[] leftDP = robTree(node.left); // 左子树的 dp 数组
        int[] rightDP = robTree(node.right); // 右子树的 dp 数组

        res[1] = node.val + leftDP[0] + rightDP[0]; //偷当前节点，那么左右子节点就不偷
        res[0] = Math.max(leftDP[0],leftDP[1]) + Math.max(rightDP[0],rightDP[1]); // 不偷当前节点，那么就把左右节点各自得到最大值加起来
        return res; // {不偷，偷}
    }
}




class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
